import java.util.ArrayList;
import java.util.List;

public class test_24_09_04 {
    class Solution01 {
        public class ListNode {
            int val;
            ListNode next;
            ListNode() {}
            ListNode(int val) {this.val = val;}
            ListNode(int val, ListNode next) {this.val = val;this.next = next;}
        }

        public ListNode rotateRight(ListNode head, int k) {
            ListNode rear = head;
            ListNode node = head;
            // 特殊情况分析：
            if (head == null || head.next == null || k == 0)
                return head;
            int count = 1;
            while (rear.next != null) {
                rear = rear.next;
                count++;
            }
            rear.next = head;
            // 链表成环
            int n = count - k % count;
            for (int i = 1; i < n; i++) {
                node = node.next;
            }
            ListNode ans = node.next;
            node.next = null;
            return ans;
        }

        class Solution02 {
            public boolean isPalindrome(ListNode head) {
                // 特殊情况
                if (head == null || head.next == null)
                    return true;
                List<Integer> arr = new ArrayList<>();
                ListNode node = head;
                // 计算链表的总长
                while (node != null) {
                    arr.add(node.val);
                    node = node.next;
                }
                int n = arr.size() - 1;
                for (int i = 0; i < n; i++) {
                    if (arr.get(i) != arr.get(n - i))
                        return false;
                }
                return true;
            }
        }

        class Solution03 {
            public ListNode oddEvenList(ListNode head) {
                if (head == null || head.next == null) {
                    return head;
                }
                ListNode evenhead = head.next, oddhead = head;
                ListNode temp = evenhead;
                while (evenhead != null && evenhead.next != null) {

                    oddhead.next = evenhead.next;
                    oddhead = oddhead.next;
                    evenhead.next = oddhead.next;
                    evenhead = evenhead.next;
                }
                oddhead.next = temp;
                return head;
            }
        }
    }

}
